#ifndef DF_MAZE_H
#define DF_MAZE_H

#include <vector>
#include <mapbase.h>
#include <random>
#include <iostream>
#include <array>

inline std::vector<std::vector<int>> df_maze(Coord<int> size){
    std::vector<std::vector<int>> result;
    std::vector<std::vector<bool>> visited;
    int visitedCount = size.x/2*size.y/2;
    std::vector<std::vector<Coord<int>>> parent;
    result = {(long long unsigned int)size.x,std::vector<int>((long long unsigned int)size.y, Blocks::wall)};
    visited = {(long long unsigned int)size.x/2,std::vector<bool>((long long unsigned int)size.y/2, false)};
    parent = {(long long unsigned int)size.x/2,std::vector<Coord<int>>((long long unsigned int)size.y/2, {0,0})};

    std::vector<Coord<int>> availDirect;
    std::array<Coord<int>, 4> direct = {Coord<int>(-1, 0),Coord<int>(1, 0),Coord<int>(0, -1),Coord<int>(0, 1)};
    Coord<int> point={0,0};
    visited[point.x][point.y]=true;
    srand(time(NULL));
    // 探索
    auto extendable = [&](Coord<int> coord)->bool{
        if(coord.x<0 || coord.x>size.x/2-1 || coord.y<0 || coord.y>size.y/2-1) return false; // 越界
        if(visited[coord.x][coord.y]) return false; // 已经访问
        return true;
    };
    auto extend = [&](Coord<int> d){
        point += d;
        visited[point.x][point.y] = true;
        visitedCount--;
        parent[point.x][point.y] = d;
    };
    while(visitedCount>1){
        availDirect.clear();
        for(auto c : direct)if(extendable(point+c)) availDirect.push_back(c);
        if(availDirect.size()==0){
            point -= parent[point.x][point.y]; // 回溯
        }else{
            int d = rand()%availDirect.size();
            extend(availDirect[d]);
        }
    }
    // tianchong
    for(int i=0;i<size.x;i++)
        for(int j=0;j<size.y;j++)
            if(i%2==0 && j%2==0)result[i][j]=Blocks::floor;
    for(int i=0;i<size.x/2;i++)
        for(int j=0;j<size.y/2;j++)
        {
            Coord<int> p = {i*2,j*2};
            Coord<int> d = parent[i][j];
            result[p.x-d.x][p.y-d.y] = Blocks::floor;
        }
    return result;
}


#endif